{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "# 8 高级特性（一）：面向对象"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 1.学生成绩排序（类与对象练习）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "设计一个学生类(Student)，其中的数据成员有：字符串类型sname表示录入的学生姓名，整型值mscore代表学生的数学成绩，整型值cscore代表学生的语文成绩，整型值escore代表学生的英语成绩。\n",
    "\n",
    "然后要求根据录入的学生成绩（各不相同），输出总分最高的学生姓名和各科目成绩。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "输入分为4个部分：\n",
    "\n",
    "先输入学生姓名，以空格分隔；\n",
    "\n",
    "然后输入学生的数学成绩（各不相同的正整数），也以空格分隔；\n",
    "\n",
    "再输入学生的语文数学成绩（各不相同的正整数），也以空格分隔。\n",
    "\n",
    "最后输入学生的英语数学成绩（各不相同的正整数），也以空格分隔。\n",
    "\n",
    "学生姓名个数和成绩个数一定会相同。\n",
    "\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为总分最高的学生姓名和各科目成绩，以空格分隔。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```shell\n",
    "jack tom\n",
    "\n",
    "95 84\n",
    "\n",
    "90 75\n",
    "\n",
    "85 90\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```shell\n",
    "jack 95 90 85\n",
    "```"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "jack 95 90 85\n"
     ]
    }
   ],
   "source": [
    "class Student:\n",
    "\n",
    "    # 4 个属性\n",
    "    def __init__(self, sname, mscore, cscore, escore):\n",
    "        self.sname = sname\n",
    "        self.mscore = mscore\n",
    "        self.cscore = cscore\n",
    "        self.escore = escore\n",
    "    \n",
    "    # 求和\n",
    "    def total(self):\n",
    "        return self.mscore + self.cscore + self.escore\n",
    "\n",
    "    # 设置按总分降序的规则\n",
    "    def __lt__(self, other):\n",
    "        return self.total() > other.total()\n",
    "\n",
    "\n",
    "# 输入\n",
    "name = input().split()\n",
    "math = list(map(int, input().split()))\n",
    "chinese = list(map(int, input().split()))\n",
    "english = list(map(int, input().split()))\n",
    "\n",
    "# 测试\n",
    "# name = ['jack', 'tom']\n",
    "# math = [95, 84]\n",
    "# chinese = [90, 75]\n",
    "# english = [85, 90]\n",
    "\n",
    "st = []  # 存储每一个学生的信息\n",
    "\n",
    "for i in range(len(name)):\n",
    "    st.append(Student(name[i], math[i],  chinese[i], english[i]))\n",
    "\n",
    "st.sort()\n",
    "print(\"%s %d %d %d\" % (st[0].sname, st[0].mscore, st[0].cscore, st[0].escore))"
   ]
  },
  {
   "source": [
    "## 2.两数求和问题"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "给定一个列表和一个整数目标，其中列表中的元素都为整数，要求返回列表中的两个元素的索引编号（以列表形式打印,为确保结果唯一，小的编号在前），使这两个元素的和为这个特定的目标。\n",
    "\n",
    "(只对应确定的唯一一组解，并且不能使用同一个元素两次。)\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共两行，第一行为列表中的元素值（各不相同），以空格隔开，第二行为一个整数。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个列表。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```shell\n",
    "0 2 3\n",
    "\n",
    "5\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "\n",
    "```shell\n",
    "[1, 2]\n",
    "```"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[1, 2]\n"
     ]
    }
   ],
   "source": [
    "# 定义一个函数，该函数能求出组合 C(n, c)\n",
    "def combination(n, c, com=1, limit=0, per=[]):\n",
    "    for pos in range(limit, n):\n",
    "        t = per + [pos]\n",
    "        if len(set(t)) == len(t):\n",
    "            if len(t) == c:\n",
    "                yield [pos,]\n",
    "            else:\n",
    "                for result in combination(n, c, com, com*pos, per + [pos,]):\n",
    "                    yield [pos,] + result\n",
    "\n",
    "\n",
    "# 输入\n",
    "diff_num = list(map(int, input().split()))\n",
    "sum_ = int(input())\n",
    "\n",
    "# 判断是否满足条件\n",
    "for res in combination(len(diff_num), 2):\n",
    "    sum_tmp = diff_num[res[0]] + diff_num[res[1]]\n",
    "    if sum_tmp == sum_:\n",
    "        index = res\n",
    "        break\n",
    "\n",
    "# 小数的索引编号在前\n",
    "if diff_num[res[0]] > diff_num[res[1]]:\n",
    "    print([res[1], res[0]])\n",
    "else:\n",
    "    print(res)"
   ]
  },
  {
   "source": [
    "## 3.\"精致\"的数"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "给定两个非负整数x和y，如果某一整数等于x^i+y^j，其中整数i>= 0且j>=0，那么我们认为该整数是一个\"精致\"的数。返回值小于或等于n(n<=200)的所有精致的数组成的列表。\n",
    "\n",
    "结果列表中每个值最多出现一次，同时请使用sorted保证结果唯一。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共三行，每一行为一个整数，分别是x y n\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个列表。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```shell\n",
    "1\n",
    "\n",
    "2\n",
    "\n",
    "5\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```shell\n",
    "[2, 3, 5]\n",
    "```\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[2, 3, 5]\n"
     ]
    }
   ],
   "source": [
    "x = int(input())\n",
    "y = int(input())\n",
    "n = int(input())\n",
    "\n",
    "tmp = []\n",
    "\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        delicate_num = x ** i + y ** j\n",
    "        if delicate_num <= n:\n",
    "            tmp.append(delicate_num)\n",
    "\n",
    "tmp = list(set(tmp))  # 用集合 set 确保元素不重复\n",
    "tmp.sort()  # 排序确保结果唯一\n",
    "print(tmp)"
   ]
  },
  {
   "source": [
    "**PS: ** 这种写法虽然能得出答案，但执行效率并不高"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 4.最大的周长"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "给定一个列表alist，alist由一些正整数（代表长度）组成，返回由alist中的三个长度组成的有效三角形的最大周长。如果所有的长度组合都不能构成有效三角形，则返回 0。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，列表中的元素以空格隔开。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个非负整数，是最大三角形的周长\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```shell\n",
    "2 1 2\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```shell\n",
    "5\n",
    "```"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "11\n"
     ]
    }
   ],
   "source": [
    "# 定义一个函数，该函数能求出组合 C(n, c)，该函数返回的是索引值列表\n",
    "def combination(n, c, com=1, limit=0, per=[]):\n",
    "    for pos in range(limit, n):\n",
    "        t = per + [pos]\n",
    "        if len(set(t)) == len(t):\n",
    "            if len(t) == c:\n",
    "                yield [pos,]\n",
    "            else:\n",
    "                for result in combination(n, c, com, com*pos, per + [pos,]):\n",
    "                    yield [pos,] + result\n",
    "\n",
    "\n",
    "alist = list(map(int, input().split()))  # 输入\n",
    "all_comb = []  # 存储所有能构成三角形的长度之和\n",
    "\n",
    "# 若记组合为 C(n, c)，则在此题情况中，n = len(alist)，c = 3\n",
    "for res in combination(len(alist), 3):\n",
    "    candidate = [alist[i] for i in res]\n",
    "    candidate.sort()  # 排序，最小两边之和大于第三边则可构成三角形\n",
    "    if candidate[0] + candidate[1] > candidate[2]:\n",
    "        all_comb.append(sum(candidate))\n",
    "\n",
    "if all_comb == []:  # 若为空列表，说明没有能构成三角形的组合\n",
    "    print(0)\n",
    "else:  # 输出最大的周长\n",
    "    print(max(all_comb))"
   ]
  },
  {
   "source": [
    "**解题思路：**\n",
    "\n",
    "首先，此题需要求出所有三个长度的组合；其次，在所有组合里判断这些长度能否构成三角形；最后，求出所有有效三角形的周长，并返回其中的最大值。\n",
    "\n",
    "而该题和上述*第 2 题*的难点都在于求组合的函数，该函数有两个特殊点：\n",
    "\n",
    "* 该函数是 `generator` 即生成器；\n",
    "\n",
    "* 使用到了*递归*。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "关于求组合的函数，感谢 [hitszjsy](https://github.com/hitszjsy) 提供了一个更为高效的方式，如下："
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 求从begin开始的n个数中 选出c个数的所有组合\n",
    "def combination(n, c, begin=0):\n",
    "    if c == 0:\n",
    "        yield []  # 结束条件\n",
    "\n",
    "    for i in range(begin, begin+n):\n",
    "        m = n + begin - i - 1  # 计算从i+1起到最后共有多少个数\n",
    "        for result in combination(m, c-1, begin=i+1):\n",
    "            yield [i] + result  # 递推"
   ]
  }
 ]
}